"""
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

    插入一个字符
    删除一个字符
    替换一个字符
首先定义状态矩阵，dp[m][n]，其中m为word1的长度+1，n为word2的长度+1，为什么+1？因为要考虑如果word1或word2为空的情况，后面可以看到。

定义dp[i][j]为word1中前i
个字符组成的串，与word2中前j

个字符组成的串的编辑距离。

插入操作：在word1的前i
个字符后插入一个字符，使得插入的字符等于新加入的word2[j]。这里要考虑清楚，插入操作对于原word1字符来说，i

是没有前进的，而对于word2来说是前进了一位然后两个字符串才相等的。所以此时是dp[i][j]=dp[i][j-1]+1。

删除操作：在word1的第i−1​
个字符后删除一个字符，使得删除后的字符串word[:i-1]与word2[:j]相同。
这里要考虑清楚，删除操作对于原word2字符来说，j−1​是没有前进的，而对于word1来说是删除了一位然后两个字符串才相等的。所以此时是dp[i][j]=dp[i-1][j]+(0 or 1)。
"""
class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m=len(word1)+1
        n=len(word2)+1
        dp = [[0 for i in range(n)] for j in range(m)]#(m+1)*（n+1）二维矩阵
        for i in range(n):
            dp[0][i]=i
        for i in range(m):
            dp[i][0]=i
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1, dp[i-1][j-1]+(0 if word1[i-1]==word2[j-1] else 1))
        return dp[m-1][n-1]